package 典型.回溯法;

import java.util.ArrayList;

// 二叉树路径 https://www.nowcoder.com/practice/b7362e784e3e34731af99065031301bca?tpId=13&tqId=11177&tPage=2&rp=2&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class JZ24 {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        if (root == null) return list;
        find(list, list1, root, target);
        return list;
    }

    public void find(ArrayList<ArrayList<Integer>> list, ArrayList<Integer> list1, TreeNode root, int target) {
        if (root == null) return;
        list1.add(root.val);
        target -= root.val;
        if (target == 0 && root.right == null && root.left == null)
            list.add(new ArrayList<Integer>(list1));
        find(list, list1, root.left, target);
        find(list, list1, root.right, target);
        //复原才能回溯
        list1.remove(list1.size() - 1);
    }
}